package com.leetcode;

/**
 * 208. 实现 Trie (前缀树)
 * 使用数组来固定维护26分叉, 空间浪费严重, 而且分叉树固定无法改动, 但是速度更快一点
 *
 * DFS 递归 版本, dfs 普遍会更快一点点
 *
 * @author fy
 * @date 2022/4/19 10:12
 */
public class Solution208_3 {
    class Trie {

        private Trie[] children;
        private boolean isEnd;

        public Trie() {
            this.children = new Trie[26];
            this.isEnd = false;
        }

        public void insert(String word) {
            dfsInsert(word, 0, this);
        }

        public boolean search(String word) {
            Trie node = dfsSearch(word, 0, this);
            return node != null && node.isEnd;
        }

        public boolean startsWith(String prefix) {
            return dfsSearch(prefix, 0, this) != null;
        }

        private void dfsInsert(String word, int index, Trie node) {
            char ch = word.charAt(index);
            int idx = ch - 'a';
            if (node.children[idx] == null) {
                node.children[idx] = new Trie();
            }
            node = node.children[idx];
            if (word.length() - 1 == index) {
                node.isEnd = true;
                return;
            }
            dfsInsert(word, index + 1, node);
        }

        private Trie dfsSearch(String prefix, int index, Trie node) {
            char ch = prefix.charAt(index);
            int idx = ch - 'a';
            if (index == prefix.length() - 1) {
                return node.children[idx];
            }
            if (node.children[idx] == null) {
                return null;
            }
            return dfsSearch(prefix, index + 1, node.children[idx]);
        }

    }

}
